<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    /**
 * @param {TreeNode} root
 * @param {TreeNode} target
 * @param {number} k
 * @return {number[]}
 */
    var distanceK = function (root, target, k) {
      let parentMap = new Map()
      function traverse(node, parentNode) {
        if (node === null) return
        parentMap.set(node.val, parentNode)
        traverse(node.left, node)
        traverse(node.right, node)
      }
      traverse(root, null)

      let visited = new Set()
      visited.add(target.val)
      let q = []
      q.push(target)
      let res = []
      let dist = 0

      while (q.length > 0) {
        let sz = q.length
        for (let i = 0; i < sz; i++) {
          let cur = q.shift()
          if (dist === k) {
            res.push(cur.val)
          }
          let parentNode = parentMap.get(cur.val)
          if (parentNode !== null && !visited.has(parentNode.val)) {
            q.push(parentNode)
            visited.add(parentNode.val)
          }
          if (cur.left !== null && !visited.has(cur.left.val)) {
            q.push(cur.left)
            visited.add(cur.left.val)
          }
          if (cur.right !== null && !visited.has(cur.right.val)) {
            q.push(cur.right)
            visited.add(cur.right.val)
          }
        }
        dist++
      }

      return res
    };
    console.log(distanceK());
  </script>
</body>

</html>